개요
QR 분해(QR Decom)는 선형 대수에서 행렬 직교행렬(Orth Matrix)과 상각행렬(Upperangular Matrix)의 곱으로 분해하는 기법이다. 주어진 $ m \ n $ 실수 또는소수 행렬 $ A $에 대해 다음과 표현할 수 있다$$
A = QR
$$
여기서:
- $ Q $는 m \times m $ 크기의 **직교렬** (실수일 경우) 또는 **유니터리 행렬** (복소수일 경우)이며, $ Q^T Q = $ (또는 $ Q^ Q = I $)를 만족한다.
- $ R $은 $ m \times n $ 크기의 상삼각행렬*(Upper Triangular Matrix)이며, 아래쪽 삼각 영역의 원소가 모두0이다.
QR 분해는 선형 연립방정식의 해법, 최소제곱법, 고유값 계산 등 수선형대수의 다양한 분야에서 핵심적인 역할을 한다.
목적과 활용
QR 분해는 다음과 같은 수치 계 문제에서 유용하게 사용된다:
- 선형 연립방정의 해법: 특히 행렬이 정방행렬이 아닐 경우
- 최소제곱 문제(Least Squares Problem): $ \min \|Ax - b\| $ 형태의 문제 해결
- 고유값 알고리즘의 기초: QR 알고리즘의 전처리 단계
- 행렬의 조건수 분석 및 수치 안정성 확보
QR 분해는 LU 분해와 달리 항상 존재하며, 행렬이 열이 선형 독립일 경우 유일하게 결정된다.
분해 방법
QR 분해를 수행하는 대표적인 알고리즘은 다음 세 가지이다.
1. 그람-슈미트 과정 (Gram-Schmidt Process)
그람-슈미트 직교화는 벡터 집합을 직교 기저로 변환하는 방법으로, QR 분해를 직관적으로 이해할 수 있게 한다.
과정 개요:
행렬 $ A $의 열벡터 $ a_1, a_2, \dots, a_n $에 대해 직교 벡터 $ q_1, q_2, \dots, q_n $을 생성하고, 이를 정규화하여 $ Q $를 구성한다. 이 과정에서 $ R $의 원소는 투영 계수로 얻어진다.
$$
q_k = a_k - \sum_{j=1}^{k-1} \langle a_k, q_j \rangle q_j, \quad \text{정규화 후 } Q = [q_1, \dots, q_n]
$$
$$
R_{jk} = \langle q_j, a_k \rangle \quad (j \leq k)
$$
단점: 수치적으로 불안정할 수 있음 (특히 고차원에서)
개선 방법: 수정된 그람-슈미트(MGS) 사용
2. 하우스홀더 변환 (Householder Reflections)
하우스홀더 변환은 벡터를 특정 평면에 대해 반사하는 선형 변환으로, 행렬을 점진적으로 상삼각형 만든다.
특징:
- 수치적으로 매우 안정적
- 대칭행렬이나 밴드 행렬에 적합
- 전체 행렬을 상삼각형으로 변환
과정:
각 단계에서 하우스홀더 행렬 $ H_k $를 구성하여 $ A $의 아래쪽 원소를 0으로 만든다. 최종적으로:
$$
H_n \cdots H_1 A = R \quad \Rightarrow \quad A = QR, \quad Q = H_1 \cdots H_n
$$
$ Q $는 직교행렬의 곱이므로 직교이다.
3. 기븐스 회전 (Givens Rotations)
기븐스 회전은 특정 평면 내에서 벡터를 회전시켜 특정 원소를 0으로 만드는 방법이다.
특징:
- 희소 행렬이나 밴드 행렬에 효율적
- 병렬 처리에 유리
- 계산량은 하우스홀더보다 큼
활용:
특정 원소 하나를 정밀하게 0으로 만들 수 있어, 제한된 위치의 소거가 필요할 때 유용하다.
예시
다음과 같은 행렬 $ A $를 QR 분해해 보자:
$$
A = \begin{bmatrix}
1 & 2 \\
1 & 3 \\
0 & 1
\end{bmatrix}
$$
하우스홀더 방법을 사용하여 분해하면:
- 첫 번째 열 벡터 $ [1, 1, 0]^T $를 $ [r, 0, 0]^T $ 형태로 변환
- 하우스홀더 행렬 $ H_1 $ 생성
- $ H_1 A $를 계산하여 첫 번째 열 아래를 0으로 만듦
- 두 번째 단계에서 두 번째 열 아래를 0으로 만들기 위한 $ H_2 $ 적용
최종적으로 $ Q $와 $ R $을 얻게 되며, $ A = QR $이 성립함을 확인할 수 있다.
수치적 고려사항
- 안정성: 하우스홀더 > 기븐스 > 그람-슈미트 (수치적 안정성 순)
- 계산 복잡도: $ O(mn^2) $ (보통 $ m \geq n $일 때)
- 메모리 사용: $ Q $를 명시적으로 저장할 경우 메모리 소모가 큼 → $ Q $를 암묵적으로 저장하는 방법 사용
관련 알고리즘 및 확장
- QR 알고리즘: QR 분해를 반복하여 고유값을 계산하는 알고리즘
- 반복 QR 분해: 희소 행렬 또는 대규모 문제에 적용
- 수치적 랭크 추정: QR 분해와 피보팅(Pivoting)을 결합하여 행렬의 랭크 추정
참고 자료 및 관련 문서
- Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
- Trefethen, L. N., & Bau, D. (1997). Numerical Linear Algebra. SIAM.
- 관련 위키 문서:
- LU 분해
- SVD 분해
- 최소제곱법
QR 분해는 수치계산의 핵심 도구로, 알고리즘의 선택은 문제의 크기, 구조, 정밀도 요구사항에 따라 달라진다. 안정성과 효율성을 고려하여 적절한 방법을 선택하는 것이 중요하다.
# QR 분해
## 개요
QR 분해(QR Decom)는 선형 대수에서 행렬 직교행렬(Orth Matrix)과 상각행렬(Upperangular Matrix)의 곱으로 분해하는 기법이다. 주어진 $ m \ n $ 실수 또는소수 행렬 $ A $에 대해 다음과 표현할 수 있다$$
A = QR
$$
여기서:
- $ Q $는 m \times m $ 크기의 **직교렬** (실수일 경우) 또는 **유니터리 행렬** (복소수일 경우)이며, $ Q^T Q = $ (또는 $ Q^* Q = I $)를 만족한다.
- $ R $은 $ m \times n $ 크기의 **상삼각행렬**(Upper Triangular Matrix)이며, 아래쪽 삼각 영역의 원소가 모두0이다.
QR 분해는 선형 연립방정식의 해법, 최소제곱법, 고유값 계산 등 수선형대수의 다양한 분야에서 핵심적인 역할을 한다.
---
## 목적과 활용
QR 분해는 다음과 같은 수치 계 문제에서 유용하게 사용된다:
- **선형 연립방정의 해법**: 특히 행렬이 정방행렬이 아닐 경우
- **최소제곱 문제**(Least Squares Problem): $ \min \|Ax - b\| $ 형태의 문제 해결
- **고유값 알고리즘의 기초**: QR 알고리즘의 전처리 단계
- **행렬의 조건수 분석 및 수치 안정성 확보**
QR 분해는 LU 분해와 달리 항상 존재하며, 행렬이 열이 선형 독립일 경우 유일하게 결정된다.
---
## 분해 방법
QR 분해를 수행하는 대표적인 알고리즘은 다음 세 가지이다.
### 1. 그람-슈미트 과정 (Gram-Schmidt Process)
그람-슈미트 직교화는 벡터 집합을 직교 기저로 변환하는 방법으로, QR 분해를 직관적으로 이해할 수 있게 한다.
#### 과정 개요:
행렬 $ A $의 열벡터 $ a_1, a_2, \dots, a_n $에 대해 직교 벡터 $ q_1, q_2, \dots, q_n $을 생성하고, 이를 정규화하여 $ Q $를 구성한다. 이 과정에서 $ R $의 원소는 투영 계수로 얻어진다.
$$
q_k = a_k - \sum_{j=1}^{k-1} \langle a_k, q_j \rangle q_j, \quad \text{정규화 후 } Q = [q_1, \dots, q_n]
$$
$$
R_{jk} = \langle q_j, a_k \rangle \quad (j \leq k)
$$
**단점**: 수치적으로 불안정할 수 있음 (특히 고차원에서)
**개선 방법**: 수정된 그람-슈미트(MGS) 사용
---
### 2. 하우스홀더 변환 (Householder Reflections)
하우스홀더 변환은 벡터를 특정 평면에 대해 반사하는 선형 변환으로, 행렬을 점진적으로 상삼각형 만든다.
#### 특징:
- 수치적으로 매우 안정적
- 대칭행렬이나 밴드 행렬에 적합
- 전체 행렬을 상삼각형으로 변환
#### 과정:
각 단계에서 하우스홀더 행렬 $ H_k $를 구성하여 $ A $의 아래쪽 원소를 0으로 만든다. 최종적으로:
$$
H_n \cdots H_1 A = R \quad \Rightarrow \quad A = QR, \quad Q = H_1 \cdots H_n
$$
$ Q $는 직교행렬의 곱이므로 직교이다.
---
### 3. 기븐스 회전 (Givens Rotations)
기븐스 회전은 특정 평면 내에서 벡터를 회전시켜 특정 원소를 0으로 만드는 방법이다.
#### 특징:
- 희소 행렬이나 밴드 행렬에 효율적
- 병렬 처리에 유리
- 계산량은 하우스홀더보다 큼
#### 활용:
특정 원소 하나를 정밀하게 0으로 만들 수 있어, 제한된 위치의 소거가 필요할 때 유용하다.
---
## 예시
다음과 같은 행렬 $ A $를 QR 분해해 보자:
$$
A = \begin{bmatrix}
1 & 2 \\
1 & 3 \\
0 & 1
\end{bmatrix}
$$
**하우스홀더 방법을 사용**하여 분해하면:
1. 첫 번째 열 벡터 $ [1, 1, 0]^T $를 $ [r, 0, 0]^T $ 형태로 변환
2. 하우스홀더 행렬 $ H_1 $ 생성
3. $ H_1 A $를 계산하여 첫 번째 열 아래를 0으로 만듦
4. 두 번째 단계에서 두 번째 열 아래를 0으로 만들기 위한 $ H_2 $ 적용
최종적으로 $ Q $와 $ R $을 얻게 되며, $ A = QR $이 성립함을 확인할 수 있다.
---
## 수치적 고려사항
- **안정성**: 하우스홀더 > 기븐스 > 그람-슈미트 (수치적 안정성 순)
- **계산 복잡도**: $ O(mn^2) $ (보통 $ m \geq n $일 때)
- **메모리 사용**: $ Q $를 명시적으로 저장할 경우 메모리 소모가 큼 → $ Q $를 암묵적으로 저장하는 방법 사용
---
## 관련 알고리즘 및 확장
- **QR 알고리즘**: QR 분해를 반복하여 고유값을 계산하는 알고리즘
- **반복 QR 분해**: 희소 행렬 또는 대규모 문제에 적용
- **수치적 랭크 추정**: QR 분해와 피보팅(Pivoting)을 결합하여 행렬의 랭크 추정
---
## 참고 자료 및 관련 문서
- Golub, G. H., & Van Loan, C. F. (2013). *Matrix Computations* (4th ed.). Johns Hopkins University Press.
- Trefethen, L. N., & Bau, D. (1997). *Numerical Linear Algebra*. SIAM.
- 관련 위키 문서:
- [LU 분해](https://ko.wikipedia.org/wiki/LU_분해)
- [SVD 분해](https://ko.wikipedia.org/wiki/특이값_분해)
- [최소제곱법](https://ko.wikipedia.org/wiki/최소제곱법)
---
QR 분해는 수치계산의 핵심 도구로, 알고리즘의 선택은 문제의 크기, 구조, 정밀도 요구사항에 따라 달라진다. 안정성과 효율성을 고려하여 적절한 방법을 선택하는 것이 중요하다.